package leetcode_2401_2500;

import java.util.Arrays;

public class LeeCode_2416 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(sumPrefixScores(new String[]{"abc"})));
    }
    private static class Tree{
        int count;
        Tree[] next = new Tree[26];

        public Tree(int count) {
            this.count = count;
        }
    }
    private static int[] sumPrefixScores(String[] words) {
        Tree tree = new Tree(0);
        for (String word : words) {
            int len = word.length();
            Tree tmp  =tree;
            for (int i = 0; i < len; i++) {
                char c = word.charAt(i);
                int index = c - 'a';
                if (tmp.next[index] == null){
                    tmp.next[index] = new Tree(1);
                }else {
                    tmp.next[index].count++;
                }
                tmp = tmp.next[index];
            }
        }
        int n = words.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            String word = words[i];
            Tree tmp = tree;
            for (int j = 0; j < word.length(); j++) {
                char c = word.charAt(j);
                int index  = c - 'a';
                tmp = tmp.next[index];
                ans[i] += tmp.count;
            }
        }
        return ans;
    }
}